Byzantine Agreement with Optimal Early Stopping, Optimal Resilience and Polynomial Complexity

摘要

We provide the first protocol that solves Byzantine agreement with optimalearly stopping ($\min\{f+2,t+1\}$ rounds) and optimal resilience ($n>3t$) usingpolynomial message size and computation. All previous approaches obtained sub-optimal results and used resolve rulesthat looked only at the immediate children in the EIG (\emph{ExponentialInformation Gathering}) tree. At the heart of our solution are new resolverules that look at multiple layers of the EIG tree.